I. Field of the Invention
The present invention relates to a method of transform data compression which obtains data representing an original image using as few bits as possible while retaining satisfactory image reconstruction capabilities.
II. Background Information
Many different approaches to image data compression have been attempted. In recent years the preferred technique of image data compression has employed transform coding, with the resultant methodology referred to as transform data compression. Transform data compression techniques yield high compression ratios with only small losses in resultant reconstructed image quality.
A detailed analysis of transform coding or transform data compression can be found in a work by R. J. Clarke, "Transform Coding of Images," Academic Press, London, 1985. In general, transform data compression involves spatially partitioning an image into many sub-images or blocks of pixel data. Subsequently, independently for each block, the following operations are performed:
(1) Transformation: A transform operator, such as the Discrete Cosine Transform (DCT) is applied to pixel data representative of that portion of the image on each block, resulting in a block of transform coefficients for each block. These transform coefficients contain all the information that was in the original pixel data for each block. However, the distribution of that information is now in the frequency domain as opposed to being in the spatial domain. That is to say, the transform coefficients each have a magnitude and frequency component. The transform operator has information compacting properties. As a consequence, a large fraction of the original image information is contained in the magnitude components of a small subset of the transform coefficients. This is the basis of transform coding. Only the magnitude components of the resultant small subset of transform coefficients now need be saved to retrieve the original information in each corresponding block of the original image. PA1 (2) Coefficient Selection: As noted above, only a small subset of transform coefficients need be selected and further processed. Several approaches have been tried, such as picking only those coefficients with magnitude components above a certain threshold or picking the coefficients with the "n" largest magnitude components. Using a small subset of coefficients requires that the magnitude components of the individual selected coefficients be retained for further processing. In addition, each set of coefficients is organized into a matrix based on the frequency components of the coefficients and the location in that matrix is identified and retained of those coefficients whose magnitude component is to be retained. Location information is required during decompression or expansion of the compressed image. PA1 (3) Quantization: The dynamic range of the coefficient magnitudes components may exceed the dynamic range of the spatial pixel data itself. In order to achieve compression, the dynamic range of the saved coefficient magnitude components must be reduced. This may be done by a many-to-one mapping procedure. For example, a simple linear operator such as dividing all coefficient magnitude components by a known constant could be employed. Nonlinear operators can also be employed. Some amount of error will be introduced by this procedure, with the magnitude of the error depending on the quantization operator used and the probability distribution of the pixel data values. PA1 (4) Coding: After quantization, additional compression may be obtained by assigning variable length code words to each quantized magnitude component. The length of the code words is based on the frequency of occurrence of each quantized magnitude component. Frequently occurring quantized magnitude components may have short codes, while rarely occurring values have long codes. The overall number of bits used to save the quantized magnitude components can thereby be reduced. Huffman coding procedure is known to be optimal and is the most commonly used technique.
One approach to saving location information has been to insert run-length counts for the coefficients that have not been selected. These run-length counts give a count of the number of consecutive, deleted coefficients. The run-length counts are inserted, in the order of occurrence, into the stream of selected coefficient magnitudes.
In each known prior art method of transform data compression there are two significant drawbacks with the coefficient selection schemes employed. First, the resultant image reconstruction data contains both coefficient magnitudes and run-length counts of deleted coefficients. This intermingling of data requires the processor of the resultant data to employ a decision-making step, which significantly increases the data processing time involved. Second, since matrix location information is saved as run-length counts, which utilize a significant amount of the fixed total number of bits available, there are fewer bits available for saving coefficient magnitudes, which results in a degradation of the image quality.
It is, accordingly, an object of the present invention to provide an improved method of compression and, in particular, an improved method of coefficient selection.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description or may be learned by practice of the invention.